package com.example.algorithms.others;

/**
 * @Author Zhang Jie
 * @Date 10/20/20
 * @Version 1.0
 */

import java.util.Random;

/**
 * 水塘抽样
 * 一种随即概率算法
 */
public class ReservoirSampling {
    /**
     * 给一个未知长度的链表，请设计一个算法，每个元素被选中的概率都是1/n，不可以有统计意义上的偏差
     * 只能遍历一次，随机地返回链表中的一个节点
     * 这里的随机是均匀随机，如果有n个元素，每个元素被选中的概率都是1/n
     * 当你遇到第i个元素时，应该有1/i的概率选择该元素，1-1/i的概率保持原有的选择
     */
    public static int uniformRandom(ListNode head){
        Random r = new Random();
        int i=0,res=0;
        ListNode p = head;
        //while循环遍历链表
        while(p!=null){
            //生成一个[0,i)之间的整数，这个整数等于0的概率就是i/1
            if(r.nextInt(++i)==0){
                res=p.value;
            }
            p=p.next;
        }
        return res;
    }

    public static class ListNode{
        public int value;
        public ListNode next;
    }

    /**
     * 给一个未知长度的序列，如果在其中随机地选择k个元素？
     * 如果要随机选择k个数，只要在第i个元素处以k/i的概率选择该元素，以1-k/i的概率保持原有选择即可。
     */
    public static int[] randomK(ListNode head, int k){
        Random r = new Random();
        int[] res = new int[k];
        ListNode p = head;
        int i;
        //前k个元素先默认选上
        for(i=0;i<k&&p!=null;i++){
            res[i]=p.value;
            p=p.next;
        }
        //while循环遍历链表
        while(p!=null){
            //生成一个【0，i）之间的整数
            int j=r.nextInt(++i);
            //这个整数小于k的概率是k/i
            if(j<k){
                res[j]=p.value;
            }
            p=p.next;
        }
        return res;
    }
}
